package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
 *
 * 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 * 1,5,11,5
 *
 * 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
 *1,2,3,5
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 *
 * 转化成01背包问题来求解
 * target值为数组总和的一半，将target的值视为背包的总空间，然后数组元素为各个位置的重量和价值，求出最后的最大价值之后将最大价值和
 * target进行比较，如果等于target，则表示能分割成两个元素和相等的子集
 */
// 二维数组版本
public class CanPartition {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String[] strings = scanner.nextLine().split(",");
            int[] nums = new int[strings.length];
            int sum = 0;
            for (int i = 0; i < strings.length; i ++) {
                if (!strings[i].equals("")) {
                    nums[i] = Integer.parseInt(strings[i]);
                    sum += Integer.parseInt(strings[i]);
                }
            }
            if (sum % 2 != 0) {
                System.out.println("false");
            } else {
                int target = sum / 2;
                int[][] dp = new int[nums.length + 1][target + 1];
                // 其实可以不用单独初始化，因为int数组如果不赋值的话默认值就是0，而初始化也是将他们置为0
//                for (int i = 0; i <= nums.length; i ++) {
//                    dp[i][0] = 0;
//
//                }
                for (int i = 1; i <= nums.length; i ++) {
                    for (int j = 1; j <= target; j ++) {
                        if (j < nums[i - 1]) {
                            dp[i][j] = dp[i - 1][j];
                        } else {
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
                        }
                    }
                }
                if (dp[nums.length][target] == target) {
                    System.out.println("true");
                } else {
                    System.out.println("false");
                }
            }
        }
    }

}
